package basic.study.wantOffer.chapter2;

/**
 * @author Kevin
 * @date 2020/5/2 20:25
 * 旋转数组
 */
public class Problem10 {

    public static int findMin(int[] arr) {
        int left = 0;
        int right = arr.length -1;
        if (arr[right] > arr[left]) {
            try {
                throw new Exception("非旋转数组");
            } catch (Exception e) {
                e.printStackTrace();
                return -1;
            }
        }
        while (left < right) {
            int mid = left + (right - left) >> 1;
            //对于{1, 0, 1, 1, 1}之类的特殊处理
            if (arr[mid] == arr[left] && arr[mid] == arr[right]) {
                return searchMin(arr, left, right);
            }
            if (right - left == 1) {
                break;
            }
            if (arr[mid] >= arr[right]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return arr[right];
    }

    public static int searchMin(int[] arr, int left, int right) {
        int result = arr[left];
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < result)
                result = arr[i];
        }
        return result;
    }
}
